<?php
/**
 * User: LRZ
 * Date: 2020/2/25
 * Time: 14:54
 */

$array1 = [4, 4, 6, 5, 3, 2, 8, 1];
$array2 = [4, 7, 6, 5, 3, 2, 8, 1];
recursiveQuickSort($array1, 0, count($array1) - 1);
stackQuickSort($array2, 0, count($array2) - 1);
print_r($array1);
print_r($array2);

/**
 * 快速排序 - 递归实现
 * @param $array
 * @param $startIndex
 * @param $endIndex
 */
function recursiveQuickSort(&$array, $startIndex, $endIndex)
{
    // 递归结束条件
    if ($startIndex >= $endIndex) {
        return;
    }
    // 找到基准元素的位置 - 单边循环法
    $pivotIndex = partition($array, $startIndex, $endIndex);
    // 基于基准元素的左部分排序
    recursiveQuickSort($array, $startIndex, $pivotIndex - 1);
    // 基于基准元素的有部分排序
    recursiveQuickSort($array, $pivotIndex + 1, $endIndex);
}

/**
 * 快速排序 - 栈实现
 * @param $array
 * @param $startIndex
 * @param $endIndex
 */
function stackQuickSort(&$array, $startIndex, $endIndex)
{
    // 定义一个栈，用来代替递归的函数栈
    $quickSortStack = new SplStack();
    // 将数列的起止下标，以数组的形式入栈
    $rootParam = [
        'startIndex' => $startIndex,
        'endIndex'   => $endIndex
    ];
    $quickSortStack->push($rootParam);

    // 循环结束条件：栈为空时
    while (!$quickSortStack->isEmpty()) {
        // 栈顶元素出栈，获取到起止下标
        $param = $quickSortStack->pop();
        // 找到基准元素的位置 - 双边循环法
        $pivotIndex = partitionV2($array, $param['startIndex']);
        // 根据基准元素分成两部分，把每一部分的起止下标入栈
        if ($param['startIndex'] < $pivotIndex - 1) {
            $leftParam = [
                'startIndex' => $param['startIndex'],
                'endIndex'   => $pivotIndex - 1
            ];
            $quickSortStack->push($leftParam);
        }
        if ($pivotIndex + 1 < $param['endIndex']) {
            $rightParam = [
                'startIndex' => $pivotIndex + 1,
                'endIndex'   => $param['endIndex']
            ];
            $quickSortStack->push($rightParam);
        }
    }
}

/**
 * 分治 - 单边循环法
 * @param $array
 * @param $startIndex
 * @param $endIndex
 * @return int
 */
function partition(&$array, $startIndex, $endIndex)
{
    /*
     * 单边循环法实现过程：
     *   1. 首先选定基准元素pivot，并设置mark指针指向数列起始位置，并开始遍历数列
     *   2. 如果遍历到的元素比基准元素大，就继续往后遍历
     *      如果遍历到的元素比基准元素小，则需要做两件事：
     *          a. mark指针右移一位，因为小于pivot的区域边界增大了。
     *          b. 当前元素和mark指针指向的元素互换位置，因为当前元素归属于小于pivot的区域
     *   3. 最后把mark指针指向的元素与pivot元素互换位置
     */

    // 取第一个位置的元素为基准元素（也可以选择随机位置）
    $pivot = $array[$startIndex];
    // mark指针表示小于基准元素的区域边界
    $mark = $startIndex;
    for ($i = $startIndex + 1; $i <= $endIndex; $i++) {
        if ($pivot > $array[$i]) {
            $mark++;
            $tmp          = $array[$mark];
            $array[$mark] = $array[$i];
            $array[$i]    = $tmp;
        }
    }
    $array[$startIndex] = $array[$mark];
    $array[$mark]       = $pivot;
    return $mark;
}

/**
 * 分治 - 双边循环法
 * @param $array
 * @param $startIndex
 * @return int
 */
function partitionV2(&$array, $startIndex)
{
    /*
     * 双边循环法实现过程：
     *   1. 首先选定基准元素pivot，并设置两个指针left和right，分别指向最左和最右两个元素，并开始循环
     *   2. 循环从right指针开始，让指针指向的元素与基准元素进行比较。如果大于pivot，指针向左移一位；如果小于pivot，则right指针停止移动，切换到left指针
     *   3. 轮到left指针开始行动，让指针指向的元素与基准元素进行比较。如果小于或等于pivot，指针向右移一位，如果大于pivot，则left指针停止移动，随后让left和right指针所指向的元素进行互换，并重新切换到right指针
     *   4. 按照2、3步骤的思路往复循环，直至left与right重合，最后把pivot和重合点元素互换
     */

    // 取第一个位置的元素为基准元素（也可以选择随机位置）
    $pivot = $array[$startIndex];
    // 设置左右指针
    $left  = 0;
    $right = count($array) - 1;

    // 当左右指针重合时，循环结束
    while ($left !== $right) {
        // 控制right指针比较并左移
        while ($left < $right && $array[$right] > $pivot) {
            $right--;
        }
        // 控制left指针比较并右移
        while ($left < $right && $array[$left] <= $pivot) {
            $left++;
        }
        // 交换left和right指针所指向的元素
        if ($left < $right) {
            $tmp           = $array[$left];
            $array[$left]  = $array[$right];
            $array[$right] = $tmp;
        }
    }

    // pivot和重合点元素互换
    if ($left === $right) {
        $array[$startIndex] = $array[$left];
        $array[$left]       = $pivot;
    }

    return $left;
}